public class Main {
    private int[][] a;
    private int[][] vis;
    private int m;
    private int n;

    public int solution(int m, int n, int[][] a) {
        assert m == a.length;
        for (int[] row : a) {
            assert row.length == n;
        }

        this.a = a;
        this.m = m;
        this.n = n;
        this.vis = new int[m][n];

        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = Math.max(res, dfs(i, j, 0));
                res = Math.max(res, dfs(i, j, 1));
            }
        }
        return res;
    }

    private int dfs(int x, int y, int k) {
        int ans = 0;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        for (int[] dir : directions) {
            int nx = x + dir[0];
            int ny = y + dir[1];

            if (nx < 0 || ny < 0 || nx >= m || ny >= n || vis[nx][ny] == 1) {
                continue;
            }

            if ((k == 0 && a[nx][ny] <= a[x][y]) || (k == 1 && a[nx][ny] >= a[x][y])) {
                continue;
            }

            vis[x][y] = 1;
            ans = Math.max(ans, dfs(nx, ny, k ^ 1) + 1);
            vis[x][y] = 0;
        }
        return ans;
    }

    public static void main(String[] args) {
        Main s = new Main();
        System.out.println(s.solution(2, 2, new int[][]{{1, 2}, {4, 3}}) == 3);
        System.out.println(s.solution(3, 3, new int[][]{{10, 1, 6}, {5, 9, 3}, {7, 2, 4}}) == 8);
        System.out.println(s.solution(4, 4, new int[][]{{8, 3, 2, 1}, {4, 7, 6, 5}, {12, 11, 10, 9}, {16, 15, 14, 13}}) == 11);
    }
}
